00100				COMPUTER VISION
00200	    				  
00300			 Thomas O. Binford, Stanford University 
00400					and
00500			Jay M. Tenenbaum, Stanford Research Institute
00600	
00700	
00800				Introduction
00900	
01000	"Intelligent" computers require knowledge of their environment, and the
01100	most effective means of acquiring such knowledge is by seeing. Vision
01200	opens  a  new  realm  of computer applications. Weather analysis from
01300	cloud maps and medical diagnosis from x-rays and  blood  cell  counts
01400	are  two  of  many  high volume  data  processing tasks that require
01500	pictorial input.  Man-machine communication will be facilitated if  a
01600	person  can  directly  show  the  computer a real object, rather than
01700	describe it symbolically.  Designers,  for  example,  could
01800	then  easily  obtain  a  computerized  structural  analysis  of scale
01900	models.
02000	
02100	A particularly exciting area of application is industrial automation.
02200	Today  in  industry  there are hundreds of machines called industrial
02300	robots.   These programmable manipulators can repetitively execute  a
02400	precise  sequence  of motions, but have no sensors and are thus unable
02500	to  react  dynamically  to  contingencies.    Simple  sensors  and  a
02600	minicomputer   could,   at   slight   additional   cost,  turn  these
02700	manipulators into true robots. With primitive visual  skills,machines
02800	could align mating parts in assembly operations, increase reliability
02900	by self-calibration, detect flaws and avoid  disasters.  Vision  will
03000	also  minimize  the  present need for precise positioning of parts at
03100	each work station; parts could instead be transported in  a  bin  and
03200	picked out as needed.
03300	
03400	The  study  of  perception also provides valuable insights into human
03500	and machine information processing. Many of the problems  encountered
03600	are  fundamental to intelligent activity: How is knowledge represented?    How
03700	does it guide in drawing conclusions from perceptual data?  How  does
03800	existing  knowledge  interact with conclusions drawn from an image to
03900	acheive learning?  Questions that arise in the implementation of  vision
04000	systems  have  broad  relevance  to  computer science:   How shoulc a
04100	complex task be partitioned into  modules?  How  should  the  modules
04200	communicate  to share their knowledge and special capabilities?   How
04300	should systems with highly interdependent modules  be  structured  to
04400	facilitate modification?
04500	
04600	Techniques developed for machine perception cannot be taken literally
04700	as models for biological systems because of differences  in  hardware
04800	and  gaps  in  our knowledge.    However, fundamental limitations are
04900	shared, suggesting that some of the principles might also be found in
05000	nature.  Computer vision research may, in turn, occasionally borrow from biology,
05100	but we cannot copy nature, since again, the details are not yet known
05200	and the hardware is different.
05300	
05400	
05500	Historically,  computer  vision  emerged  from  the  study   of   two
05600	dimensional  pattern  recognition.  However, it is seldom possible to
05700	apply the mathematical formalisms developed for classification to the
05800	analysis  of  real  scenes.  Consider  the visual requirements for an
05900	organism such as a robot. It must manipulate or  avoid  objects,  not
06000	just  classify  them.        Manipulation  requires three-dimensional
06100	interpretations and spatial relations of objects.  In  problems  such as
06200	character  recognition,  it  was  attractive to simply save images or
06300	feature vectors, and then match against an image or part of an image. But
06400	in  real  scenes,  objects  occlude one another, they have parts with
06500	joints that move separately, there are many viewpoints, many possible
06600	objects,  and many combinations of objects. Object classes, moreover,
06700	are often defined by function, not shape (e.g., the  class  of  coffee
06800	cups).    Direct  template  matching  techniques  are impractical for
06900	these requirements, except in very carefully controlled applications.
07000	Perception  involves  complex  deductions  in order to  understand an image in
07100	terms of a priori knowledge of the world.
07200			ELEMENTS OF A VISUAL SYSTEM
07300	
07400	The  computer  eye is usually some form of TV camera with color filters and a
07500	turret or zoom lens  for  closeup  views.     The  computer  controls
07600	filters,  lens  and  other  parameters to optimize the image for each
07700	task [1].   A recent  study  has  suggested  alternative
07800	sensors  to  overcome  the  inadequate  dynamic  range  of television
07900	systems [2].  Range  information  greatly  simplifies  the
08000	interpretation  of scenes. Humans use depth information obtained from
08100	stereo and a variety of inferred cues such as motion parallax and the
08200	size  of  known  objects.  Since  these techniques require subtantial
08300	processing, it is easier for  machines  to  obtain  depth  by  direct
08400	measurement.  Several  depth sensors based on triangulation have been
08500	built [3, 4].
08600	
08700	A TV image is read  into  memory  as  an  array  of  brightness  values
08800	(typically 300x300) with 4 to  8 bits for each sample for each color. Computer
08900	vision can be thought of as the process  of  transforming  this  mass  of  numbers  into  a  symbolic
09000	description. The translation process can be subdivided  into segmentation,
09100	representation, and interpretation.
09200	
09300	The process  of  segmentation  partitions  a  scene  into  meaningful
09400	entities  that  may  be recognizable.      Segmentation in character
09500	recognition  is  simple  since  printed  characters   are   spatially
09600	separated  and  have  high contrast with white paper. It is harder to
09700	segment objects in a real scene (even simple  scenes)  since  objects
09800	may  overlap  and  will  not  usually  be  separable  from  the local
09900	background by a single attribute like brightness  contrast.  Instead,
10000	segmentation  must  proceed by seeking regions of uniform brightness,
10100	color, or texture (itself a  complex  descriptor),  or  regions  with
10200	regular  boundaries.  Segmentation  may also depend on inferred depth
10300	cues (e.g., texture gradients or suspected occlusion).
10400	
10500	In what form can we represent objects internally in the computer? The
10600	simplest  form is a pictorial template, an array of brightness values
10700	to be matched directly against fragments of  scenes  by  correlation.
10800	Given  the  inadequacies  of  this  representation,  we must describe
10900	partitioned regions symbolically in terms of extracted features  such as
11000	color,  size,  texture, and shape.  All these properties are inferred
11100	from the image by complex processes.  Simple descriptors for shape or
11200	texture  may be used in simple tasks and limited context. Shape might
11300	be described by the ratio of the squared perimeter to the area  of  a
11400	region.  More sophisticated shape representations, needed for a wider
11500	range of tasks, are described later.
11600	
11700	Interpretation is often expressed as  computing  a  distance  measure
11800	between  an  object and a stored model.  For simple cases that approach can be
11900	useful.     When objects are occluded, there must be a partial match.
12000	When  objects  are  not  identical, judgments of similarity depend on
12100	representation of shape and representation of the task, in  order  to
12200	define  important  differences.  The most useful approach is to build
12300	up  symbolic  descriptions  and   make   symbolic   descriptions   of
12400	differences.    Sometimes  there are sufficiently few  models that matching
12500	with each model is possible. More generally,  the  observed  features
12600	must  first  be  used  to  retrieve likely models from a large visual
12700	memory.
12800	
12900	The integration of segmentation, representation and interpretation to
13000	achieve perception is illustrated by a system built at the University
13100	of Edinburgh [5]  that  can  recognize  a  small  set  of
13200	ordinary  objects such as pencils, eyeglasses and teacups.   Objects
13300	are presented  against  a  contrasting  background.  Segmentation  is
13400	achieved   by   partitioning   the  scene  into  regions  of  uniform
13500	brightness. Objects are represented by  relational  graphs  detailing
13600	gross attributes (e.g., size and shape) of their principal regions and pairwise
13700	constraints  between  these regions (e.g., above, larger than).     Interpretation  is  accomplished   by
13800	mapping  the  relational graph descriptions of known objects onto the
13900	segmented regions obtained from the scene and seeking the best match.
14000	
14100	Experience with early bottom-up systems  of  this  type  led  to  the
14200	realization  that  the  three  basic processes of a perceptual system
14300	were highly interdependent; one cannot proceed  sequentially  through
14400	segmentation,  representation, and interpretation and expect to obtain
14500	a globally consistent interpretation for all objects in a scene.  One
14600	problem  is  that  no  reliable  basis  exists for judging the global
14700	significance  of  segmentation  boundaries  using  local   similarity
14800	criteria.  Segmentation  must  be  guided by interpretation to choose
14900	among many alternative partitionings, the alternative that leads to a  globally
15000	consistent and reasonable description of the scene. A nice exposition
15100	of these ideas is given by Minsky [6].
15200	
15300				BLOCKS WORLD
15400	
15500	To avoid some of these difficulties, research concentrated  initially
15600	on  scenes  of toy blocks.  Roberts' [7] important work opened the
15700	field.  Objects were represented as built up of three primitive
15800	parts,  a  block, a wedge, and a hexagonal prism. The program assumed that
15900	it would first obtain perfect  line  drawings.  Interpretation  meant
16000	choosing  a  stored  three-dimensional model which, after translation,
16100	rotation, and scaling, could be projected to match part of  the  image.
16200	The  recognized piece was then cut away and the remainder considered.
16300	Primitives were represented by their vertices in three dimensions. To
16400	decide  on  likely  image points that belonged to a single body, the
16500	program attempted to identify unobscured polygons, and then match sets of
16600	vertices  to topologically similar model vertices. Line drawings were
16700	formed by a sequence of local operations.  Candidate edge points were
16800	considered  by thresholding the gradient of intensity.  Isolated edge
16900	points were discarded.   Connected line fragments  were  concatenated
17000	into  lines  that  were  segmented  at corners by a sequential least
17100	squares line fit.  Merging of colinear lines bridged some gaps.
17200	
17300	That system organization has proven inadequate. It is not  enough  to
17400	use  models and template matching. Producing perfect line drawings is
17500	not practical.    Some lines are  missed;  shadows,  reflections  and
17600	surface  markings  cause  extra  lines; errors made at one stage are
17700	compounded by later stages.  These deficiencies motivated  subsequent
17800	research.
17900	
18000	Guzman  [8]  found  it  possible  to  segment  complex scenes into
18100	objects without template matching, by observing  that  some  vertices
18200	give local evidence that adjacent regions belong to the same body. In
18300	Figure 1, vertices  A,B,C,E,G,H and  I  give  evidence  that  adjacent
18400	regions  belong  to the same body, while vertex F does not.  Vertex D,
18500	which  resembles  G,  gives  misleading  evidence.   To   avoid   such
18600	coincidences,  the program required confirmation.      Regions linked
18700	twice were joined into clusters; regions linked twice  to  a  cluster
18800	were  also  joined. Regions linked only to a single cluster were also
18900	joined to that cluster. Eventually the program  evolved  to  include
19000	inhibitions  against certain links by requiring similar conditions at
19100	both ends of  a  line.  Other  links  were  introduced  without  much
19200	motivation.
19300	
19400	This  program  was an important advance.    Bodies could be segmented
19500	without recognition and without explicit models.    The  program  did
19600	surprisingly   well,   but   had   problems   with  holes  and  other
19700	non-convexities, and with  accidental  alignment.    being  told  the
19800	background.    Guzman  also  could  not cope well with imperfect line
19900	drawings. For example, in the case of Figure  2  his program would fail because  a  missing  line
20000	makes  region  R3 common to both the block and wedge. Falk [9] was
20100	able to avoid some of the errors associated with  missing  boundaries
20200	by  using  an approach resembling Guzman's to link line segments likely to
20300	belong to the same object instead of regions.
20400	
20500	The limited generality of both these programs was  due  to  the  fact
20600	that  they  were  implemented as a collection of ad hoc heuristics for
20700	segmentation with no explicit understanding of line drawings.   Thus,
20800	while  Falk himself realized that regions like R3 were non-planer and
20900	could not arise in a scene  containing  only  trihedral  solids,  his
21000	program  could  not  reason  at this level. Huffman [10] and Clowes
21100	[11] made theoretical  analyses  of  objects  with  only  trihedral
21200	vertices (three planes at each vertex).  Using these analyses, edges could be classified at each
21300	vertex as convex, concave  and  obscuring. Some drawings could then be
21400	rejected  as  impossible if a given line was not consistently labeled
21500	at each end. Waltz [12] expanded that labeling of lines to include
21600	cracks  and  whether  adjacent  regions were shadowed or illuminated.
21700	Since each vertex could have many interpretations. it would seem that
21800	a search for consistent labelings would be unmanageable.     Instead,
21900	the increased precision of descriptions allows  rapid  discarding  of
22000	wrong  interpretations.     Not only are solutions possible, they are
22100	quickly obtained. Instead of a complete tree search, it was  adequate
22200	to   consider   vertices   in   sequence,   eliminating  inconsistent
22300	interpretations as each new vertex was  added.    This  produced  all
22400	possible  interpretations  of a scene. However, 
22405	in   cases   with ambiguous  interpretations   
22450	some evaluations could be made to choose
22500	reasonable  interpretations.  
22650	A  detailed  survey of the work through
22700	Huffman appears in a recent text by Duda and Hart [13].
22800	
22900	
23000	
23100	
23200	
23300	The best performance in  extracting  line  drawings  from  television
23400	images   of  polyhedra  is  given  by  the  Shirai  [14]  and  the
23500	Binford-Horn [15]  line  finders.   Shirai's  system  performs
23600	better,  but  requires  large contrast between objects and background
23700	(e.g., white on black), and finds only features and objects for which
23800	cues  are available from context.     The Binford-Horn system is able
23900	to find most lines in a scene of white blocks on a  white  background
24000	in  arbitrary  lighting.  It  misses a few lines, which can usually be
24100	inferred from those that  were  found,  and  garbles  some  vertices.
24200	The two systems are complementary and should be combined.
24300	
24400	The two programs are based on different principles.  Shirai's program
24500	first found the outer boundaries of an object or cluster of  objects.
24600	It  then  tried  to  guess  additional  lines  that  were  parallel,
24700	perpendicular, or extensions  to  lines  already  found.   Search  for
24800	missing lines concentrated around vertices in the preliminary drawing
24900	where they would be most likely found. The use  of  context  involved
25000	not changing thresholds, but using special-purpose operators--e.g.,  verify
25100	a line at known position and angle; find a  line  through  a  vertex.
25200	Figure  3  illustrates  the  complexity of scenes handled by Shirai's
25300	program. The Binford-Horn system was intended to provide the base for
25400	a system such as Shirai's by providing a partial line drawing without
25500	special assumptions about the scene.  It  used  a  local  directional
25600	edge operator and an optimal sequential decision process to group the
25700	edge points into continuous curves.
25800	
25900	It is interesting to compare these systems with biological ones.  The
26000	directional  edge  operators  [16], which  are  scanned  over the image, are
26100	analogous to  the  edge-detector  cells  discovered  by  Heubel  and
26200	Wiesel[17]  in  higher  animals.     In  practice, large brightness
26300	gradients at reflections and  on  curved  surfaces  cause  masses  of
26400	spurious  edge  fragments.     Smooth  gradients  are  eliminated  by
26500	subtracting the local average at each point,  a  process  similar  to
26600	lateral inhibition in the retina of animals.
26700	
26800	
26900	
27000				REAL-WORLD VISION
27100	
27200	
27300	
27400	The   blocks   world   illustrates  many  basic  aspects  of  machine
27500	perception.   However, since many critical  problems  encountered  in
27600	perceiving  real-world  scenes  do  not arise in the blocks world, few of the techniques
27700	developed extend to the real-world domain. For example:
27800	
28100	(1) The region-growing and edge-finding techniques developed for uniformly painted blocks
28200	cannot  cope  with  the  textures  and  variations of brightness that
28300	predominate in the real world.
28400	
28500	(2) The precise topological  descriptions  that  characterized  simple
28600	polyhedra  are  inappropriate  or unobtainable for complex real world
28700	objects such as trees.
28800	
28900	(3) Interpretation  by  exhaustively  matching  all  known  prototypes
29000	against  each  segmented  body  is not feasible with large numbers of
29100	objects and cluttered scenes.
29200	
29300	Description of simple polyhedral scenes was  difficult  enough;  with
29400	these  added  obstacles,  is there hope for success in perceiving the
29500	real world?    Perception in  the  blocks  world  sought  a  complete
29600	description  of  everything  present. It may not be possible (or even
29700	meaningful)  to  obtain  exhaustive  descriptions  of  real   scenes.
29800	However,  complete  descriptions  are  seldom  needed;  a  system  is
29900	typically concerned with only a few objects required  to  complete  a
30000	specific task.
30100	
30200	For  blocks, we restricted our programs to black and white images and
30300	distinguished structures of blocks solely on the basis of shape.   In
30400	the  real  world, there is a tremendous redundancy of visual cues. We
30500	can use color, texture, depth, size, and surface orientation, as well
30600	as   shape,   whichever   distinguishes   a  particular  object  most
30700	effectively.
30800	
30900	Real-world objects are usually found in well defined contexts--e.g.,
31000	telephones   are  expected  on  tables  but  not  in  waste  baskets.
31100	Recognition of a few prominent  landmarks,  combined  with  a  priori
31200	knowledge  of the environment can thus severely restrict what objects
31300	may be present in each part of the scene. While these objects may  be
31400	difficult   to  describe,  there  will  usually  be  sufficient  cues
31500	available to discriminate easily among the  alternatives.    Often,
31600	very gross descriptions of complex attributes such as shape will suffice
31700	to  discriminate  among    a  limited  number  of  grossly  different
31800	alternatives  (e.g.,  a person can be distinguished from a dog simply
31900	by the predominantly vertical orientation of a human body).
32000	
32100	Real-world vision can be viewed as a strategy problem: Given a  task,
32200	first  decide  where  to look for objects of interest and then decide
32300	how to distinguish  them  from  other  objects  that  might  also  be
32400	present.   The system must limit interpretations to a small subset of
32500	possible objects, selected on the basis of a priori expectations  and
32600	crude  descriptions  of  the  scene.    Segmentation  can be based on
32700	attributes that are known to be uniform over these objects. The  key
32800	problems of information overload are overcome by tightly coordinating
32900	segmentation and interpretation with world knowledge and task  goals.
33000	The overload problem cannot be solved by merely building faster computers and
33100	bigger memories; hardware improvements will aid  adequate  techniques
33200	but do little for exhaustive techniques.
33300	
33400	The  principal  work to date on real world vision has concentrated on
33500	segmentation and representation.  Segmentation of textured scenes has
33600	been  studies as a two-dimensional problem for agricultural and earth
33700	resource survey applications.  Bajcsy  [18]  has  analyzed  outdoor
33800	scenes with perspective, where three-dimensional texture descriptions
33900	are important.      Textures were described hierarchically  in  terms
34000	of   simpler   texture  elements  and  their  spatial  relationships.
34100	Descriptors for texture elements  and  relations  were  derived  from
34200	Fourier  analysis.   Typical attributes were directionality (if any),
34300	size, contrast, and spacing  of  texture  elements.      The  Fourier
34400	transform  was  found troublesome,however, and color descriptors were
34500	added to improve performance.  Some depth relations could be observed
34600	from  texture  gradient.     An attempt was made to obtain consistent
34700	interpretations by first confirming region boundaries by  independent
34800	properties,  making  three-dimensional  interpretations, and matching
34900	region descriptors with those of sky, trees, grass, etc.  in a  world
35000	model.
35100	
35200	The  quality  of  interpretation  was  limited  by  unreliability  of
35300	region-growing processes. Further work in outdoor scenes attempts  to
35400	incorporate  the  world  model  and  interpretation  into  the region
35500	growing process. Regions are merged not only because of similarity of
35600	properties, but because the consistency of semantic interpretation is
35700	improved.
35800	
35900	
36000	Typical  robot  tasks  such  as  manipulation,  collision  avoidance,
36100	display, and recognition  were  analyzed  to  determine  computational
36200	primitives  required  for descriptions of shape.  Although some would
36300	disagree, our criteria for shape representation are [19]:
36400	
36500	(1) Representations should be symbolic at a high  level  in  order  to
36600	interface with knowledge of the problem domain.
36700	
36800	(2)  Representations  should  depend on segmentation into parts, which
36900	may have sub-parts.
37000	
37100	(3) Primitives should be three-dimensional volume descriptions, rather
37200	than surface descriptions, to allow a natural choice of parts.
37300	
37400	(4)  Descriptions  should  be  generative.     A  modest collection of
37500	primitives should allow description of a vast set of objects.
37600	
37700	We will outline one representation that fulfils these desiderata  for
37800	a  large  class  of curved objects. Objects are described in terms of
37900	components that are simple to describe,  and  the  relationships  of
38000	these  parts.  A useful shape primitive for many curved objects is an
38100	arbitrary space curve, and  normal  cross-sections  along  this  axis
38200	(Figure  4).      Snake-like  objects,  helices, toroids, and locally
38300	helical and toroidal shapes are naturally described [19]. Our
38400	basic  definition of a simple piece is that the direction of its axis
38500	be continuous and that the cross-section function along that axis  be
38600	continuous.    We  look  for large changes in the cross-section, and
38700	consider them as likely places  for  segmenting  the  object.     The
38800	segmentation  process must be flexible and able to generate alternative
38900	propositions.   A higher-level routine will  ultimately  select  from
39000	the  alternatives.     Figure  5  shows  an  experimentally  obtained
39100	computer description of a doll [3].
39150	
39200				INDUSTRIAL APPLICATIONS
39300	
39400	Recently,  several  laboratories  have begun to apply techniques from
39500	perception  research  to  practical  industrial  tasks.      Stanford
39600	University  has  demonstrated simple assembly operations using vision
39700	and touch. General Motors laboratories has succeeded  in  mounting  a
39800	wheel  on  an axle. Stanford Research Institute and Hitachi Ltd. have
39900	each demonstrated systems that can distinguish sheet metal parts  on
40000	a  moving  conveyor  belt  and  determine their orientation to enable
40100	manipulation.   Template-matching  techniques  were  used  to   take
40200	advantage of the two-dimensional nature of these tasks. Moreover, the
40300	conveyor demonstrations relied on the contrast between shiny  metallic
40400	parts  and  the  black belt to simplify segmentation. Many industrial
40500	processes share similar constraints or can be readily  redesigned  to
40600	do  so.  We thus expect a proliferation of industrial applications of
40700	computer perception in the near future.